#include <iostream>
using namespace std;

template <class T>
struct list_node {
    T _val;
    list_node<T>* _next;
    list_node<T>* _prev;


    list_node(const T& data = T())
        :_val(data);
        ,_next(nullptr)
        ,_prev(nullptr)
    {}
};


template <class T>
class list {
    typedef list_node<T> Node;

private:
    void empty_init() {
        _dummy = new Node();
        _dummy->_next = _dummy;
        _dummy->_prev = _dummy;
    }

    void swap(list<T>& lt) {
        std::swap(_dummy, lt._dummy);
        std::swap(_size, lt._size);
    }

    void clear() {
        Node* cur = _dummy->_next;
        while(cur != _dummy) {
            Node* del = cur;
            cur = cur->_next;
            erase(del);
        }
    }

public:


    list() 
    {
        empty_init();
    }

    list(const list<T>& lt) {
        empty_init();
        Node* cur = lt._dummy->_next;
        while(cur != lt._dummy) {
            push_back(cur->_val);
            cur = cur->_next;
        }
    }

    list<T>& operator=(const list<T>& lt) {
        list<T> tmp_lt(lt);
        swap(tmp_lt);
        return *this;
    }

    // list<T>& operator=(list<T> lt) {
    //     swap(lt);
    //     return *this;
    // }
    ~list() {
        clear();
        delete _dummy;
    }

    // 在pos位置之前插入
    void insert(Node* pos, const T& x) {
        Node* prev = pos->_prev;

        Node* newnode = new Node(x);
        newnode->_next = pos;
        pos->_prev = newnode;
        prev->_next = newnode
        newnode->_prev = prev;

        ++_size;
    }

    void erase(Node* pos) {
        assert(pos != _dummy);
        Node* prev = pos->_prev;
        Node* next = pos->_next;

        prev->_next = next;
        next->_prev = prev;
        delete pos;
        --_size;
    }

    void push_back(const T& x) {
        insert(_dummy, x);
    }

    void push_front(const T& x) {
        insert(_dummy->_next, x);
    }

    void pop_back() {
        erase(_dummy->_prev);
    }

    void pop_front() {
        erase(_dummy->_next);
    }

private:
    Node* _dummy;
    size_t _size;
};